package offer;

/**
 * 剑指 Offer 13- I. 剪绳子 I
 * 剑指 Offer 14- II. 剪绳子 II
 */
public class CuttingRope {
    final static int MX = 1000000007;

    public static void main(String[] args) {

        System.out.println(cuttingRope1(10));
        System.out.println(cuttingRope2(54));

    }

    public static int cuttingRope1(int n) {
        if (n < 2) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int[] dps = new int[n + 1];
        dps[0] = 0;
        dps[1] = 1;
        dps[2] = 2;
        dps[3] = 3;
        int max = 0;

        for (int i = 4; i <= n; i++) {
            max = 0;
            for (int j = 0; j <= i / 2; j++) {
                int dp = dps[j] * dps[i - j];
                if (max < dp) {
                    max = dp;
                }
                dps[i] = max;
            }
        }
        max = dps[n];
        return max;

    }

    public static int cuttingRope2(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;

        double ret = 1;
        if (n % 3 == 1) {
            ret = 4;
            n = n - 4;
        }
        if (n % 3 == 2) {
            ret = 2;
            n = n - 2;
        }
        double v = (Math.pow(3, n / 3)%MX * ret);
        return (int) v;
    }

}
